Search for: All records

In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem  $f$is a minimal cover or strong minimal cover of a problem  $h$. We show that strong minimal covers only exist in the cone below  $id$and that the Weihrauch lattice above  $id$is dense. From this, we conclude that the degree of $id$is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. 

In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x 0 < a 0 is ⩽ a 1 and such that every enumeration degree x 1 < a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that every enumeration degree x < a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair. 

Abstract The tower number $${\mathfrak t}$$ and the ultrafilter number $$\mathfrak {u}$$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $$\omega $$ and the almost inclusion relation $$\subseteq ^*$$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $$(G_n)_{n \in {\mathbb N}}$$ of computable sets is a tower if $$G_0 = {\mathbb N}$$ , $$G_{n+1} \subseteq ^* G_n$$ , and $$G_n\smallsetminus G_{n+1}$$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $$G_n$$ . A tower $${\left \langle {G_n}\right \rangle }_{n\in \omega }$$ is an ultrafilter base if for each computable R , there is n such that $$G_n \subseteq ^* R$$ or $$G_n \subseteq ^* \overline R$$ ; this property implies maximality of the tower. A sequence $$(G_n)_{n \in {\mathbb N}}$$ of sets can be encoded as the “columns” of a set $$G\subseteq \mathbb N$$ . Our analogs of $${\mathfrak t}$$ and $${\mathfrak u}$$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $$\Delta ^0_2$$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively.